InforLorV4, Main, Exploration, bibRecord, 005416

Optimal Linear Arrangement of Interval Graphs

Identifieur interne : 005416 ( Main/Exploration ); précédent : 005415; suivant : 005417

Optimal Linear Arrangement of Interval Graphs

Auteurs : Johanne Cohen [France] ; Fedor Fomin [Norvège] ; Pinar Heggernes [Norvège] ; Dieter Kratsch [France] ; Gregory Kucherov [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:ADB6CA3799DAA280B0D8016371667E4EBA63ADEA

Descripteurs français

Pascal (Inist)
- Algorithme approximation, Algorithme rapide, Arithmétique intervalle, Borne inférieure, Graphe intervalle, Graphe linéaire, Informatique théorique, Intervalle temps, Permutation, Problème NP difficile, Problème agencement, Temps polynomial, Théorie graphe.

English descriptors

KwdEn :
- Approximation algorithm, Computer theory, Fast algorithm, Graph theory, Interval arithmetic, Interval graph, Layout problem, Linear graph, Lower bound, NP hard problem, Permutation, Polynomial time, Time interval.

Abstract

Abstract: We study the optimal linear arrangement (OLA) problem on interval graphs. Several linear layout problems that are NP-hard on general graphs are solvable in polynomial time on interval graphs. We prove that, quite surprisingly, optimal linear arrangement of interval graphs is NP-hard. The same result holds for permutation graphs. We present a lower bound and a simple and fast 2-approximation algorithm based on any interval model of the input graph.

Url:

https://api.istex.fr/ark:/67375/HCB-2GDVJCXJ-M/fulltext.pdf

DOI: 10.1007/11821069_24

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
</author>
<author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
</author>
<author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:ADB6CA3799DAA280B0D8016371667E4EBA63ADEA</idno>
<date when="2006" year="2006">2006</date>
<idno type="doi">10.1007/11821069_24</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-2GDVJCXJ-M/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002922</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002922</idno>
<idno type="wicri:Area/Istex/Curation">002887</idno>
<idno type="wicri:Area/Istex/Checkpoint">001269</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001269</idno>
<idno type="wicri:doubleKey">0302-9743:2006:Cohen J:optimal:linear:arrangement</idno>
<idno type="wicri:Area/Main/Merge">005562</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:08-0029305</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000350</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000675</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000362</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000362</idno>
<idno type="wicri:doubleKey">0302-9743:2006:Cohen J:optimal:linear:arrangement</idno>
<idno type="wicri:Area/Main/Merge">005767</idno>
<idno type="wicri:Area/Main/Curation">005416</idno>
<idno type="wicri:Area/Main/Exploration">005416</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA, 54506, Vandoeuvre-lès-Nancy Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<affiliation wicri:level="1"><country xml:lang="fr">Norvège</country>
<wicri:regionArea>Department of Informatics, University of Bergen, 5020, Bergen</wicri:regionArea>
<wicri:noRegion>Bergen</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Norvège</country>
</affiliation>
</author>
<author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
<affiliation wicri:level="1"><country xml:lang="fr">Norvège</country>
<wicri:regionArea>Department of Informatics, University of Bergen, 5020, Bergen</wicri:regionArea>
<wicri:noRegion>Bergen</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Norvège</country>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>LITA, Université de Metz, 57045, Metz Cedex 01</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Metz</settlement>
</placeName>
<orgName type="university">Université Paul Verlaine - Metz</orgName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LIFL/CNRS, 59655, Villeneuve d’Ascq</wicri:regionArea>
<placeName><region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
<settlement type="city">Villeneuve d’Ascq</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Computer theory</term>
<term>Fast algorithm</term>
<term>Graph theory</term>
<term>Interval arithmetic</term>
<term>Interval graph</term>
<term>Layout problem</term>
<term>Linear graph</term>
<term>Lower bound</term>
<term>NP hard problem</term>
<term>Permutation</term>
<term>Polynomial time</term>
<term>Time interval</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme approximation</term>
<term>Algorithme rapide</term>
<term>Arithmétique intervalle</term>
<term>Borne inférieure</term>
<term>Graphe intervalle</term>
<term>Graphe linéaire</term>
<term>Informatique théorique</term>
<term>Intervalle temps</term>
<term>Permutation</term>
<term>Problème NP difficile</term>
<term>Problème agencement</term>
<term>Temps polynomial</term>
<term>Théorie graphe</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We study the optimal linear arrangement (OLA) problem on interval graphs. Several linear layout problems that are NP-hard on general graphs are solvable in polynomial time on interval graphs. We prove that, quite surprisingly, optimal linear arrangement of interval graphs is NP-hard. The same result holds for permutation graphs. We present a lower bound and a simple and fast 2-approximation algorithm based on any interval model of the input graph.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Norvège</li>
</country>
<region><li>Grand Est</li>
<li>Hauts-de-France</li>
<li>Lorraine (région)</li>
<li>Nord-Pas-de-Calais</li>
</region>
<settlement><li>Metz</li>
<li>Vandœuvre-lès-Nancy</li>
<li>Villeneuve d’Ascq</li>
</settlement>
<orgName><li>Université Paul Verlaine - Metz</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
</region>
<name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
</country>
<country name="Norvège"><noRegion><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
</noRegion>
<name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
<name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005416 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005416 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:ADB6CA3799DAA280B0D8016371667E4EBA63ADEA
   |texte=   Optimal Linear Arrangement of Interval Graphs
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Optimal Linear Arrangement of Interval Graphs

Optimal Linear Arrangement of Interval Graphs

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.